演算法課程

(Algorithms)

國立聯合大學

資訊管理學系

陳士杰老師

Course 9

NP Theory序論

An Introduction to the Theory of NP

國立聯合大學資訊管理學系演算法課程 (陳士杰)

▓ Outlines

本章重點

 Polynomial Time

 Intractability

 Optimization Problems vs. Decision Problems

 The Theory of NP

{ P problem

{ NP problem

{ NP-complete problem

{ NP-hard problem

 如何証明某個問題為NP-complete問題

 近似演算法

國立聯合大學資訊管理學系演算法課程 (陳士杰)

▓ Polynomial Time (多項式時間)

什麼是 “

多項式時間

(Polynomial Time)

(Polynomial Time)”?

Polynomial

Time

Non

Polynomial

Time

國立聯合大學資訊管理學系演算法課程 (陳士杰)



Def

Def:

 一個稱為多項式時間的演算法(

Polynomial

time Algorithm

time Algorithm) 必

須符合：在合理的輸入大小 (input size)下，該演算法於最差情況

(Worst-case)的時間複雜度以多項式函數為限。

 因此，若n為input size，存在一個多項式函數

(

) ，則：



Polynomial

time computable

 一函數 f(x) 為polynomial-time computable，若且為若存在一演算

法，使得對所有的輸入 x，皆可在Polynomial Time內求得 f。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 如果我們講「這個問題很難」，這句話可能有兩種不同的

意義：

 [意義 1]: 這個問題也許目前已經有一些還不錯的近似解法，只是想

進一步找出真正最佳的方法是件困難的事

 [意義 2]: 這個問題本身就難以找出解決方法。

 第一種意思指的是對

人

人而言很困難，而第二種意思指的是

對

計算機

計算機而言很難。

 在探討問題的難度時，比較正確的講法應該是指一個問題

是

易解的

(tractable)

(tractable) 或是

難解的

(intractable)

(intractable)。

▓ Intractability (難解問題)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 在資訊科學領域中，若無法在最差情況(Worst-case)下，以多項式時間

的演算法來解決某個問題，該問題就被稱為難解 (Intractable)問題。

 一個難解的問題，必須沒有任何多項式時間的演算法可以解它。

 但是，如果有一個問題在最差情況(Worst-case)下，目前還找不到一個

Polynomial-Time Algorithm解它，但是也無法保証未來就找不到

Polynomial-Time Algorithm來解這個問題，則

無法証明

該問題是

Intractable

 For example:

{ 早期，利用

brute

force algorithm (

暴力演算法

)

) 解連鎖矩陣相乘問題

(Chained Matrix Multiplication problem) ，其時間複雜度為

non

polynomial

time

time.

{ 然而，若以

dynamic programming algorithm

dynamic programming algorithm (Algorithm 3.6) 來解，則其

時間複雜度為

(

)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 就難解性而言，問題的主要分類可分為三種:

 Problems for which polynomial-time algorithms

have been found

{ 如：最短路徑問題、MST問題、排序問題、搜尋問題…

 Problems that have been proven to be

intractable

{ 時間複雜度被証明為

指數複雜度

(

以上

)

)的問題。如：河內塔問題

{

不存在有解決問題之演算法

不存在有解決問題之演算法的問題。如：程式停止問題 (Halting

Problem)、功能相等問題(Equivalence Problem)…

 Problems that have not been proven to be intractable, but for which

polynomial-time algorithms have never been found

大多數的問題不是落在第一類，就是落在第三類。

 第三類問題中，頗具知名度的是

旅行推銷員問題

(Traveling

Salesman Problem)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

The Traveling Salesman Problem; TSP

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 TSP問題：

 一個銷售員會不斷地花費時間去拜訪n個城市。(A salesman spends

his time visiting

cities cyclically. )

 在一趟的旅程中，他只會拜訪每一個城市一次，而且當他回到原

本的起始城市後就會停止此趟的拜訪旅程。(In one tour he visits

each city exactly once, and finishes up where he started.)

 什麼樣的拜訪旅程會使該銷售員所花費的旅行距離(成本)最少？

(In what order should he visit the cities to minimize the distance

traveled?)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 若採用暴力法去解TSP問題，則會發現要找出所有可能的

路徑所花費的時間是呈

指數

(Exponentially)

(Exponentially) 成長的!!

 3 cities Æ 1 solution.

 10 cities Æ 181,440 possible tours

 n cities Æ (n-1)!/2 possible tours

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 若 n=26，則有 25! /2條不同路徑：

 25!=15511210043330985984000000≅1.55 x 10

這個數字寫來輕鬆，

究竟有多大？

 假設電腦每秒可計算 10

條路徑的成本，一年有 3.15 x 10

秒，故一

年可計算 3.15 x 10

條路徑，求出所有路徑的成本需時

 即便是對不太大的 n=26，就需時五千億年，顯然這種方法毫無用

處。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

在所有的問題當中，除了過去所討論過的各種最

佳化問題 (Optimization Problem) 以外，尚有另外

一種型態的問題:

決策問題

(Decision Problem)



Decision Problem

Decision Problem: 此類問題輸出的答案非常簡單，就

是 “

yes

yes” 或 “

no” 兩者之一。

▓ Optimization Problem vs. Decision Problem

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 The partition problem (分割問題):

 給予一組正整數的集合S={a

, a

, … , a

}，問: 是否可以將其分割成兩

個子集合S

與S

，而此兩個子集合的個別總和相等。

 Ex: Let S = {13, 2, 17, 20, 8}. The answer to this problem instance is "

yes

yes"

because we can partition S into S

= {13, 17} and S

= {2, 20, 8}.

 The Sum of Subset Problem (部份集合的和問題):

 給予一組正整數的集合S={a

, a

, … , a

}及一個常數c，問: 集合S中是

否存在一組子集合S’

，此子集合S’的數字總合為c。

 Ex: Let

= {12, 9, 33, 42, 7, 10, 5} and

= 24.

{ The answer of this problem instance is "

yes

yes" as there exists

S’

= {9, 10, 5}

and the sum of the elements in

S’

is equal to 24.

{ If

is 6, the answer will be "

no".

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 The Satisfiability Problem (滿足問題; SAT):

 給一個布林函數E，我們對存在於此函數E中的一些變數分別指派True或

False，使這個函數結果為True。

 Ex: Let E = (-x

∨ x

∨-x

)∧(x

∨ -x

) ∧(x

∨ x

). Then the following assignment

will make E true and the answer will be “

yes

yes”.

←F, x

←T

 If E is -x

∧ x

, there will be no assignment which can make E true and the

answer will be “

no”.

 此問題為第一個被証明是屬於

Complete

Complete的問題 (by S. A. Cook, 1971).

 The Minimal Spanning Tree Problem (最小擴張樹問題):

 Given a graph G, find a spanning tree T of G with

the minimum length

the minimum length.

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 The Traveling Salesperson Problem (旅行推銷員問題):

 給予一個圖G = (V,E) ，找出一個由該圖的某一點出發所構成的

cycle，此cycle會經過該圖中的每個點一次而再回到出發點，同時

其總長度為最短

 Ex: Consider following graph. There are two cycles satisfying our

condition. They are C

= a→b→e→d→c→f→aand C

= a→c→b→e

→d→f→a. C

shorter

shorter and is the solution of this problem instance.

國立聯合大學資訊管理學系演算法課程 (陳士杰)

Some problems:



The Partition Problem



The Sum of Subset Problem



The Satisfiability Problem



The Minimal Spanning Tree Problem



The Traveling Salesperson Problem

一般來說，最佳化問題(Optimization Problems)比

決策問題(Decision Problems)要來得難處理!!

(Decision Problems)

(Optimization Problems)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 最佳化問題均可找出一個與其對應的決策問題。

 For example (MST Problem):

 Given a graph

and a constant

 The total length of the spanning tree of the graph

{ If

, then the answer is

“

yes

”

”,

{

otherwise

otherwise, its answer is

“

”

”.

 這個決策版本的最小擴張樹問題，可以稱為最小擴張樹決

策問題(The minimal spanning tree decision problem)

 如果要解某個最佳化問題的決策版本(Decision version of the

optimization problem)已經很困難了，則該問題的最佳化版

本一定更難解決。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

▓ The Theory of NP

假設你在一個公司上班。有一天，上司叫你去為某

個對公司很重要的問題找出有效率的演算法。

結果，你研究了很長的一段時間，沒有任何進展，

你去找你的上司…

我想不出好方法，我可能太笨了！

國立聯合大學資訊管理學系演算法課程 (陳士杰)

我想不出好方法，

因為不可能有這種好方法！

結果，你的上司說要開除掉你這個豬頭，並由一個

演算法設計專家來取代你。此時，你很不爽地對他

說…

國立聯合大學資訊管理學系演算法課程 (陳士杰)

你的上司因為你的強辯，很不情願地再給你一段時

間去証實你說的話。

結果，你又試了很長的一段時間，還是失敗了!!此刻

的你既無法找出一個有效率的演算法，又無法証明

這樣的演算法是不存在的…

你快要被開除了

國立聯合大學資訊管理學系演算法課程 (陳士杰)

此時，你突然想起在聯合資管上演算法課程時，偉

大的杰哥所說過的一段話：

世界上很多的電腦科學家正在為旅行推銷員問題(TSP)

找尋一個較有效率的演算法。但是，到目前為止

卻沒有人能發展出一個在最差情況下，時間複雜

度比指數複雜度要來得好的TSP演算法。不過，也

沒有人証明出找到這種演算法是不可能的…

國立聯合大學資訊管理學系演算法課程 (陳士杰)

你找到了一線生機!! 因為，你只要能証明找出公司

問題之有效率演算法的難度和找出旅行推銷員問

題的有效率演算法是

一樣難

一樣難的 (亦即：兩者是同一

類的問題)，代表著上司要求你解決的問題也曾難

倒很多電腦科學家。

(你很慶幸有好好上演算法)



你終於証明出來公司的問題和旅行推銷員問題是

同一等級的…

國立聯合大學資訊管理學系演算法課程 (陳士杰)

我想不出好方法，

因為這些名人專家也不會！

你被加薪了，因為你讓公司節省了許多經費。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 思考：

 Computer Science對於電腦所處理之問題的難易區分標準為何？

 將一個問題歸類(轉化)為某一個已知問題的概念與作法為何？

 証明一些問題很難為何這麼重要？

以下課程內容所討論到的問題，若無特別說明，皆

以“決策版本

”的問題為主

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 除了不存在有解決問題之演算法的問題以外，在可以解決

的問題當中，又可以分成 “簡單問題” 和 “困難問題” 兩

類。而問題的難易之分取決於所使用的演算法類型或使用

之計算機器的類型：

所有可解決之問題

合理輸入資料

輸出結果 Yes/No

決定性演算法

(Deterministic Algo.)

非決定性演算法

(Non-deterministic Algo.)

Deterministic v.s. Non-deterministic

國立聯合大學資訊管理學系演算法課程 (陳士杰)



Deterministic Algorithm

Deterministic Algorithm (決定性演算法)

{ Def: 這類演算法在做任何事時，該演算法的下一步只有一件

事可以做。(Permitting at most one next move

at any step in a

computation)

{ 是指演算法中每一個步驟的運算都需要被唯一定義，因此

產生

的結果也是唯一

的。

{ 能夠執行決定性演算法的機器，稱為

決定性的機器

(Deterministic Machine)。電腦就是一種決定性的機器。

 由於在此類計算機器運作的演算法在處理問題時，每一步只有一

件事，因此，只要有一個處理器即可，故容易實現。

國立聯合大學資訊管理學系演算法課程 (陳士杰)



Non

deterministic Algorithm

deterministic Algorithm (非決定性演算法)

{ Def: 這類演算法在做任何事時，該演算法的下一步可能會有

無限多件事可以選擇。 (Permitting more than one choice of

next move at some step in a computation)

{ 演算法中每一個步驟的運算無法被唯一定義。

{ 能夠執行非決定性演算法的機器，稱為

非決定性的機器

非決定性的機器 (Non-

deterministic Machine)。

 由於非決定性演算法在執行時，每一步可能有無限多件事要處

理，故非決定性計算機器需假設

有

無限多

個處理器可平行處理

。

因此，非決定性計算機器的計算能力比決定性計算機器要強大。

 但是，實際上並不存在此種機器。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Non-deterministic Algorithm的執行步驟分成兩個階段：



猜測階段

(Guess)

{ 由於沒有一個既定的程序來從事此階段的猜測工作，因此本階段是

Non-deterministic

{ 對於本階段，我們只知道一件事：

 如果一個問題有正確解的話，此階段

一定

一定可以將這個正確解給猜出來；

反之，若該問題沒有正確解的話，則此階段就會

隨便

隨便給解答。

 至於猜測階段是怎麼將這個解答給找出來的，我們無從得知(不論所給的

解是否為正確解) 。



驗証階段

(Verification)

{ 將上一階段所猜出來的結果加以驗証是否為真 (True)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

Nondeterministic SAT

 以一個具有n個變數之布林函數E之滿足問題 (SAT) 為例：

 如果此問題是使用決定性演算法，則時間複雜度為O(2

)

 如果此問題是使用非決定性演算法，則時間複雜度為O(n)

/* Guess */

for i = 1 to n do

← choice(true, false);

/* Verification */

if E(x

, x

, … ,x

) is true then

success;

else failure;

國立聯合大學資訊管理學系演算法課程 (陳士杰)

Polynomial-Time Reducible (多項式時間的轉化)

 Def: 若有兩個問題Q1和Q2，其解集合分別為L1和L2：

 如果Q1可以多項式時間轉化成Q2 (即：L1 ≤

L2 或 Q1 ≤

Q2)，則

{ 存在一個函數 f(x) /*此函數不一定是實質的數學公式，也可能是一個虛的概念或意涵*/

{ 此函數 f(x) 為polynomial-time computable

{ 該函數 f(x) 使得對所有x而言，x∈L1 若且唯若 f(x)∈L2 (x∈L1 ⇔ f(x)∈L2)

 這個Reduce的作用類似 “

歸類

歸類”。Q1和Q2可被視為同一類型的問題。

f(x)

所有在L1內的元素，經f(x)轉化後必在L2中；而原

本不在L1內的元素，經f(x)轉化後則必不在L2中

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 為何要做Reduce?

 Q1 reduce 成Q2，表示Q1問題可以由處理Q2問題的演算法所解決。

Q1之Input

Reduce

Q2之Input

解Q2之Algo.

Q2之Output

Reduce

Q1之Output

即：f(x)

即：

x∈L1 ⇔ f(x)∈L2

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 前述定義隱含一些概念：

 Q1問題可以由處理Q2問題的演算法所解決。若Q2問題有一個有效

率的演算法，可以在多項式時間內將Q2問題給解掉，表示Q1問題

也一定可以在多項式時間內被解掉。

 因此，函數 f(x) 必須是要

polynomial

time computable

time computable。

{ 這是因為解Q1問題的時間相當於 “函數f(x)的轉換時間 + 解Q2問題之

演算法的解題時間” 所構成。

{ 若轉換時間過長，則解Q2問題之演算法就算是再快，也無助於加速

對Q1問題之求解。

 可表示成 L1 ∝ L2 或 Q1 ∝ Q2

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Q1 ∝ Q2的意義：

 Q2問題比Q1問題難 (雖然兩者是同一類型的問題)

 若Q2有解，則Q1就有解

 想要証明Q1和Q2一樣難，則需証出Q1 ≤

Q2 且Q2 ≤

 若Q1 ∝ Q2且Q2 ∝ Q3，則Q1 ∝ Q3 (遞移性)

 範例：假設現在有下列兩個問題：

 Q1: 一台電梯中有4個人，其中是否有三個人彼此互相認識?

 Q2:有一個4個頂點之無向圖G=(V,E)，其中是否存在一個三角形?

証明Q1 ∝

Q2。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 解：

 有一個函數f，使得：

{ 人

→頂點vi

{ 人

和人

互相認識 → (vi, vj)∈E

{ 人

和人

互不認識 → (vi, vj)∉E

 說明此函數f 為polynomial time computable

{ 因為轉換後的圖G=(V,E)，是以相鄰矩陣表示，該矩陣的大小為 |V|

。若要

將該矩陣填滿值則需時 O(|V|

)。

{ ∴函數f為Polynomial time computable

 說明該函數f(x)使得對所有x而言，x∈L1 ⇔ f(x)∈L2

{ 有三人互相認識 ⇔ 有一個三角形在圖形G中

{ (証明⇒)：人

和人

互相認識 ⇒ vi， vj和vk兩兩有邊相連⇒ vi， vj

和vk形成三角形

{ (証明⇐)：(理由同上)，人

和人

互相認識

∝

得証

此函數為一個虛的轉換概念

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 P:

 是一群Decision Problem的集合，這些問題皆可利用Deterministic

Algorithm於Worst Case的情況下，在

Polynomial Time

Polynomial Time的複雜度內

被解決

被解決。

 NP:

 所謂 “NP” 是指Non-deterministic與Polynomial兩個單字的簡寫

 這類的問題只要給個解答，可以在Polynomial Time的複雜度內很快

地

驗證

(Verify)

(Verify) 出這個解答是否正確。

{ 由於決定性演算法為非決定性演算法的一個特例，且容易找到答案也

會容易驗証答案。因此，P可視為NP的一個特例。

{ P⊂NP (

{ P=NP (

P, NP, NP hard, NP complete

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 NP-hard:

 是一群Decision Problem的集合。當 Q ∈ NP-hard 若且唯若所有屬

於NP的Decision Problem Q’ (∀Q’∈NP) 皆可

多項式時間轉化

多項式時間轉化成Q

(Q’∝Q)

 此類問題至今仍未找到一個多項式複雜度的決定性演算法，且一

般相信沒有多項式複雜度的決定性演算法存在。

 NP-complete:

 是一群Decision Problem的集合。若某一個問題Q屬於NP-

complete，則滿足以下兩個條件:

{ Q屬於

hard

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 一般而言，理論學家相信上述問題之集合圖示如下:

 NP-hard與NP-complete的關係：

 所有NP-complete問題都是NP-hard問題 (如：旅行推銷員問題)；

但是NP-hard問題不見得是NP-complete問題 (如：程式停止問

題，它不是NP問題)

 NP-complete ⊆ NP-hard

 如果有一個NP-hard問題能夠找到多項式複雜度的決定性演算法，

則所有NP-complete問題也都存在多項式複雜度的決定性演算法。

NP NP-hard

NP-

complete

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Nearly all of the decision problems are NP problems.

 In NP problems, there are some problems which have

polynomial algorithms

. They are called

P problems

P problems.



Every

P problem

must be an NP problem

must be an NP problem.

 There are a large set of problems which, up to now, have

polynomial algorithms

polynomial algorithms.

Summary

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Some important properties of

complete problems

complete problems:

 Up to now, no NP-complete problem has any worst case polynomial

algorithm.

 If any NP-complete problem can be solved in polynomial time,

NP = P

NP = P.

 If

the

decision version of an optimization problem

is NP

complete

complete,

this

optimization problem

optimization problem is called

hard



We can conclude that all

complete

and

hard

problems must be

difficult problems

because

 They do not have polynomial algorithms at present.

 It is quite unlikely that they can have polynomial algorithms in the future.

國立聯合大學資訊管理學系演算法課程 (陳士杰)

▓ 如何証明某個問題為NP-complete問題

 証明某問題為NPC的理由：

 所有的NP-complete問題都是具有相關性的。

 因此，若有一個NP-complete問題能夠找到多項式複雜度的決定性

演算法來解它，若且唯若所有NP-complete問題也都存在多項式複

雜度的決定性演算法。

 証明方法：欲証明Q∈NPC，則有以下兩個步驟：

c 証明Q∈NP (can guess an answer, and check it in polynomial time)

d 找一個已知的NPC問題 Q’ ，証明Q’∝Q (即：証明Q∈NP hard)

{ 存在一個函數f(x)，

{ 此函數f(x)為polynomial-time computable，

{ 該函數f(x)使得對所有x而言，x∈L1 若且唯若 f(x)∈L2 。

(L1為Q’問題的解集合；L2為Q問題的解集合)

(簡單)

(複雜)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

為什麼經由前面兩步驟就可以証明Q∈NPC

 理由：

 步驟 1 主要在說明Q是屬於NP問題

 步驟 2 主要在說明Q是屬於NP-hard問題

{ 因為一個NP-complete問題，它既是屬於NP問題、也是屬於NP-hard

問題。假若 Q’ 為一個已知的NP-complete問題，因此 Q’ 既是屬於NP

問題，也應該屬於NP-hard問題。

{ 因為 Q’ 有NP-hard問題的血統，因此我們可以得知所有的NP問題 ∝

Q’。(由NP-hard的定義得知)

{ 由於 “ 所有的NP問題 ∝ Q’ ”。若我們能夠証明出Q’∝Q，根據

遞移性，就可以得知所有NP問題 ∝ Q (∵所有NP問題 ∝ Q’ ∝

Q)。因此 Q 即屬於NP-hard問題。

 Q如果既是屬於NP問題，也是屬於NP-hard問題，則Q即屬於

complete

問題

問題。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

問題：

 如果每一個NP-Complete的問題都可以由另一個已知的

NP-Complete問題所推導而得，那麼：

全世界第一個NP-Complete問題是誰?

國立聯合大學資訊管理學系演算法課程 (陳士杰)

庫克定理 (Cook’s Theorem)

 SAT問題屬於NP-Complete (即：SAT∈NPC)

 如果有一個多項式時間的演算法可以解決SAT問題，則

所有屬於NP的問題都可以在多項式時間內解決

 SAT是全世界第一個被很辛苦地証明出來的NPC問題

 往後的學者所証明出之NPC問題，皆是藉由該定理所陸

續推導出來

國立聯合大學資訊管理學系演算法課程 (陳士杰)

後續NPC問題大致的推衍流程如下圖 (各家版本不一)。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

証明下列定理：

 3-SAT問題為NP-Complete

 Clique (結黨) 問題為NP-Complete

 Vertex-Cover (頂點覆蓋) 問題為NP-Complete

國立聯合大學資訊管理學系演算法課程 (陳士杰)

証明定理：3-SAT問題為NP-Complete

 何謂3-SAT問題:

 為SAT問題的特定型態。給一個SAT函數，且此函數中每一個括號

內皆恰有3個變數

，則我們對存在於此函數中的一些變數分別指派

True或False，使這個函數結果為True。

 Ex: Let E = (-x

∨ x

∨-x

)∧(x

∨ -x

∨-x

) ∧ (-x

∨ x

). Then the

following assignment will make E true and the answer will be “

yes

yes”.

←T, x

←F, x

←F

 【証明方法】欲証明Q∈NPC，則：

 証明Q∈NP (can guess an answer, and check it in polynomial time)

 找一個已知的NPC問題 Q’，証明Q’∝Q

{ 存在一個函數f(x)，

{ 此函數f(x)為polynomial-time computable，

{ 該函數f(x)使得對所有x而言，x∈L1 若且唯若 f(x)∈L2 。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 重點：Can guess an answer, and check it in polynomial time

 証明：給一個具CNF型式且每一個括號內恰含3個變數的布林函數。當

給定(猜出)一組解時，則可在Polynomial Time內驗証是否可使該函數

為true。∴3-SAT∈NP。

 由以下的非決定性演算法得知此問題在猜一組解答僅需O(n)，而驗証

解答僅需常數時間O(c)。由於可在Polynomial Time的複雜度內很快地

驗證出解答是否正確，故得知此問題為NP問題。

Guess

for i = 1 to n do

← choice(true, false);

/* Verification

if E(x

, x

, … ,x

) is true then

success;

else failure.

証明Q∈NP

國立聯合大學資訊管理學系演算法課程 (陳士杰)

証明Q’∝Q

 SAT問題是一個已知的NPC problem (by 庫克定理)。因此，我們

令它為Q’，而待驗証的3-SAT問題為Q。

 証明Q’∝Q即是說明下列三個事項:

 是否存在一個函數f(x)，可以將Q’的問題型態轉換成Q的問題型態

 此函數f(x)是否為polynomial-time computable，

 該函數f(x)是否對所有x而言，x∈L1 ⇔ f(x)∈L2

(L1為Q’問題的解集合；L2為Q問題的解集合)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 【說明事項 1】是否存在一個函數f(x) 。

 給定一個SAT問題的布林函數E，試著將此函數 E 轉換成每個括號內的變數

個數均恰有三個之新的布林函數 E’，且此新函數 E’ 不能變更原函數 E 的邏

輯意涵。若能成功轉換，則表示 Q’ 與 Q 之間確實存在一個函數 f(x)。

 由上表得知，Q’與Q之間確實存在一個函數f(x)

變數個數

函數 E 括號內情況轉換後之函數 E’

括號情況

)

∨

) ∧

∨

) ∧

∨

) ∧

∨

)

∨

)

∨

) ∧

∨

)

∨

)

不需做轉換

多於3

∨

… ∨

)

∨

) ∧

(ӯ

∨

) ∧

(ӯ

∨

) ∧

…

∧

(ӯ

k-4

∨

k-2

∨

k-3

) ∧

(ӯ

k-3

∨

k-1

∨

)

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 【說明事項 2】此函數f(x)是否為polynomial-time computable。

 假設一個 SAT 問題的布林函數 E 有 n 個括號，且每個括號中最多有 k 個

變數，則函數 E 轉換成 3-SAT 問題之布林函數 E’ 所花費的時間複雜度最

多只需要 O(nk)。

 在SAT問題的布林函數 E 中，某一個括號內的變數：

{ 若只有一個或兩個變數時，則所需的轉換時間為常數時間 (∵轉換過程固定不

變)。

{ 若有三個變數時，則不需要轉換時間，轉換時間為 0 。

{ 若有多於三個變數 (即：k > 3) 時，則需要的轉換時間函數 k-2 (∵若一個clause

有k個變數，則會轉換出k-2個clause)，時間複雜度為O(k)。

 由於可能有n個括號，因此所需要花費在轉換上的時間複雜度最多為 O(nk)

 由上述說明，可得知

此函數

f(x

)

為

polynomial

time computable

time computable。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 【說明事項 3】此函數f(x)對所有x而言，x∈L1 若且唯若 f(x)∈L2 。

(註：L1為Q’問題的解集合；L2為Q問題的解集合)

 以本題來說，要証明 “有一組解可使SAT問題的布林函數 E 為True ⇔ 有一

組解可使 3-SAT 問題的布林函數 E’ 為True”

(E is satisfiable

⇔ E′

is satisfiable

)

c 【先証 E is satisfiable ⇒ E′ is satisfiable】

{ 若要讓一個SAT問題的布林函數 E 為True，則每一個括號均要為True。

{ 若要讓一個括號為True，則此括號中至少要有一個變數為True。

⇓

{ 若有一組可讓原SAT問題之布林函數 E 為True的解，也能使轉換後的3-SAT問題

之布林函數 E’ 為True，則該組解能讓 E’ 中的每一個括號均能夠為True。

{ 將原本在SAT問題內為True之 x

變數所在的括號內的 y

變數設成False；原本在

SAT問題內為False之變數所在的括號內的 y

變數設成True，則此組解可使 E’為

True

E is True

E’ is True

國立聯合大學資訊管理學系演算法課程 (陳士杰)

d 【再証 E is satisfiable ⇐ E′ is satisfiable】

{ 若要讓一個3-SAT問題的布林函數 E’ 為True，則每一個括號均要為True。

{ 若要讓一個括號為True，則去除掉 y

變數不看，此括號中至少要有一個x

變

數為True。

⇓

{ 若有一組可讓原3-SAT問題之布林函數 E’ 為True的解，也必能使SAT問題之布

林函數 E 為True。

 由 c 與 d 的証明，可以得知 “有一組解可使SAT問題的布林函數 E 滿足

⇔ 有一組解可使 3-SAT 問題的布林函數 E’ 滿足”

 由前面一系列說明，我們可以得知

SAT

∝

SAT

SAT (∵Q’ ∝ Q)。

 更進一步地，我們可以得知 “

SAT

問題

∈

Complete Problem

Complete Problem”

E’ is True

E is True

國立聯合大學資訊管理學系演算法課程 (陳士杰)

証明定理：Clique問題為NP-Complete

 【証明方法】欲証明Clique ∈ NPC，則：

 証明Clique∈NP

 找一個已知的NPC問題 Q’，証明Q’∝Clique

{ 存在一個函數f(x)，

{ 此函數f(x)為polynomial-time computable，

{ 該函數f(x)使得對所有x而言，x∈L1 若且唯若 f(x)∈L2 。

 証明Clique∈NP

 給一個無向圖G = (V, E)。當給定(猜出)一組大小為k的頂點集合時，

則可在Polynomial Time內驗証出此組頂點集合是否為該圖形G中

Size ≥ k的Clique。(by 相鄰矩陣來驗証)∴Clique∈NP。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 找一個已知的NPC問題 Q’，証明Q’∝Clique

 令此已知的NPC為3-SAT Problem。

 存在一個函數f(x)

{ 給定一個具有k個Clause、且滿足3-SAT要求的布林函數F，透過以下

轉換步驟可將其變成一個無向圖G，且該圖G具有頂點個數≥k的

Clique，以(G, k)表示。

 對於F中的每一個Clause，建立一組頂點(Vertex)，並依該Clause的變數

名稱來標示之。

 建立頂點間的Edge。連線標準：同組不相連、矛盾不相連，其餘全部相

連。

 (G, k)中的k = F的Clause個數

國立聯合大學資訊管理學系演算法課程 (陳士杰)

{ Ex：有一個布林函數F如下：

透過上述步驟，可畫出如下的圖。

 上述過程可在Polynomial Time內做轉換

{ 將F轉為圖形G時，可用相鄰矩陣(Adjacency Matrix)表示圖形G。

{ 此相鄰矩陣大小為3n × 3n，其中n為Clause個數，3表示每個Clause內

有3個變數。

{ 故建立此圖形G僅需O(n

)。

)()()( zyxzyxzyxF ∨∨

∧

∨∨

∧

∨∨

圖形G中，k=3的Clique

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 F為Satisfiable ⇔ G有Size ≥ k的Clique

{ (由左往右)

 假設有一組解A令函數F為True，則A必使F中的每個Clause為True。

 每個Clause為True，則各個Clause內至少會有一個變數為True，且這些變

數必不會相互矛盾

。

 這些為True的變數所對應的圖形G中之頂點，在G中必兩兩有邊相連。

{ (由右往左)

 假設在圖形G中有一個頂點集合C存在，且此集合C為圖G的Clique，則此

集合C中的頂點必無兩個頂點位在同一組

；且每組必有一頂點在C中。

 令集合C中每個頂點所對應的變數為True，則可使布林函數F中的每個

Clause均有變數為True，

為

Satisfiable

Satisfiable。

 由前面一系列說明，我們可以得知

SAT

∝

Clique

Clique。

 更進一步地，我們可以得知 “

Clique

問題

∈

Complete

Problem

Problem”。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

証明定理：Vertex Cover問題為NP-Complete

 【証明方法】欲証明Vertex Cover ∈ NPC，則：

 証明Vertex Cover∈NP

 找一個已知的NPC問題 Q’，証明Q’∝Vertex Cover

{ 存在一個函數f(x)，

{ 此函數f(x)為polynomial-time computable，

{ 該函數f(x)使得對所有x而言，x∈L1 若且唯若 f(x)∈L2 。

 証明Vertex Cover∈NP

 給一個無向圖G = (V, E)。當給定(猜出)一組大小為k的頂點集合時，

則可在Polynomial Time內驗証出此組頂點集合是否為該圖形G的

Vertex Cover。(by 相鄰矩陣來驗証)∴Vertex Cover∈NP。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 找一個已知的NPC問題 Q’，証明Q’∝Vertex Cover

 令此已知的NPC為Clique Problem。

 存在一個函數f(x)

{ 設(G, k) 為Clique的一個實例，則為Vertex Cover的一個實

例。

{ Ex:

 此函數可以在Polynomial Time內，將 G 轉成

{ 即：將相鄰矩陣內的值做0/1互換，可在O(n

)內轉換完成。

k)n,G( −

k = 3 的 Clique = {a, c, e}

n-k = 2 的 VC = {b, d}

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 G有Size ≥ k的Clique ⇔ 有Size ≤ n-k的Vertex Cover

{ (由左往右)

 假設有一個頂點集合C為圖形G 的Clique，此集合C的所有頂點在G中則

兩兩有邊存在。而集合C的所有頂點在則彼此無邊。

 集合C中的頂點於圖形中若有邊存在，則該邊的另一頂點必位於V-C

的集合中。

 由於集合V-C中所有的頂點會連接圖形的所有邊，因此頂點集合V-C

為的Vertex Cover。

{ (由右往左)

 假設在圖形有一個頂點集合D存在並為該圖形的Vertex Cover，則此

集合D中的頂點與圖形上所有的邊相連。

 頂點集合V-D在圖形中彼此無邊存在，則必在圖形G中有邊相連。因

此，頂點集合V-D為圖形 G 的Clique。

 由前面一系列說明，我們可以得知

Clique

∝

Vertex Cover

Vertex Cover。

 更進一步地，我們可以得知 “

Vertex Cover

問題

∈

Complete

Problem

Problem”。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

▓ 近似演算法 (Approximation Algorithm)

 一個問題Q若屬於NP-complete問題，則代表此問題目前尚無有效率的

演算法可以解決(即：目前無法在Polynomial Time內找出最佳解) 。更

甚者，若是NP-hard問題，大概可以確定找不到有效率的演算法來解

決它了。

 然而，許多NP-complete/NP-hard的問題卻常常出現在各種領域!!若我

們退而求其次，去找尋一個

近似解

近似解而非最佳解的話，則能夠預期以有

效率的方式解決此問題。此即Approximation Algorithm的精神。

 設計一個近似演算法需注意的Issue:

 需保証近似演算法所求出的解也是該問題的可行解

 近似演算法的時間複雜度要很低 (至少要為Polynomial Time)

 用近似演算法所求出之近似可行解在最差的情況下之品質衡量，即：用近

似演算法求出來的解有多靠近最佳解

國立聯合大學資訊管理學系演算法課程 (陳士杰)

Approximation Ratio

 Approximation Ratio用來定義所求出之可行解有 “多靠近”

最佳解：

 對於某個問題而言，在給定輸入為x之情況下，令其最佳解為

Opt(x)，而利用近似演算法A所求出的解為A(x)。若此近似演算法A

為ε-approximation，則滿足：

其中，ε稱為近似演算法的Approximation Ratio。

 某問題的

近似解

近似解，與

最佳解

最佳解之間的差距

不會超過

(

或低於

)

倍

 上述不等式中的max是為了同時考量最小化與最大化問題的應用。

x. allfor ,)

A(x)

Opt(x)

A(x)

max(

≤

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 上述定義同時針對

最大化

最大化和

最小化

最小化問題之解做考量。

 若是

最小化問題

最小化問題，則會比大，因此為該問題

之Approximation ratio。此時，前述定義的不等式變為：

 若是

最大化問題

最大化問題，則會比大，因此為該問題

之Approximation ratio。此時，前述定義的不等式變為：

Opt(x)

A(x)

Opt(x)

A(x)

Opt(x)

A(x)

Opt(x)

A(x)

Opt(x)

x.allfor ,

Opt(x)

A(x)

≤

x.allfor ,

A(x)

Opt(x)

≤

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Ex. 1: Vertex-Cover Problem有一個近似演算法如下。此演算

法保証每次找到的解為一個Vertex Cover，且大小最多只比

最佳解多兩倍。

Input: G=(V, E)

Output: G的一個Vertex Cover C

Approx-VC(G)

C←∅;

E’←E;

while (E’ ≠ ∅)

{令(u, v)為E’中的任一邊;

將頂點u和v加入集合C中;

去掉E’中所有與頂點u和v相連的邊;

}

例如：給定以下之無向圖，

d h

最佳解Opt = {d, f, h}

近似解C = {c, d, e, f, g, h}

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 分析： (by近似演算法需注意的三個Issue)

 近似演算法所求出的解也是該問題的可行解

{ 在while迴圈中，line 4於每一回合會挑選出一個邊，並會在line 5中將

此邊的兩個頂點(u, v)加入集合C中，而line 6會刪除被u或v所cover到

的邊。

{ 也就是說，每一回合自E’刪除的邊均被集合C中的頂點所cover到，而

存留在E’的邊則是未被集合C中之頂點所cover。

{ 因此，當E’為空集合時，表示C中所有的頂點會cover圖中所有的邊。

故集合C是一個Vertex Cover。

 近似演算法的時間複雜度要很低

{ 演算法中的while迴圈最多跑|E|回合，故時間複雜度為O(|E|)。

 品質衡量

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 品質衡量 (續前)

{ 令集合Opt為最佳解的頂點集合 (即：Vertex Cover的規模最小)，集合

A為每回合由line 4所挑選的

邊

邊所構成之集合。

{ 由於line 5會將每個回合於line 4所挑出來的邊之兩個頂點加入到集合C

中，因此可以得知|C|=2|A|

{ 由於line 4在各個回合所挑出來的邊，彼此間不會有共同的vertex。因

此，在最佳解集合Opt裡，至少會包含集合A中的每條邊之1或2個

vertex (否則Opt內的頂點就無法cover集合A中，沒有被包含到的那些

邊!!)。所以|Opt|≥|A|

{ 綜合上面所述，可以得到 |C |=2|A|≤ 2|Opt| Ö |C |≤ 2|Opt| 。因此，

approximation ratio為2。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Ex. 2：TSP最佳化問題為NP-complete問題。課本上提出兩個

解該問題的近似演算法。

[

Algo

. 1]

此近似演算法的解與最佳解之差距 (定理9.6)：minapprox

< 2 ×

mindist

[

Algo

. 2]

此近似演算法的解與最佳解之差距 (定理9.7)：minapprox2 < 1.5

mindist

國立聯合大學資訊管理學系演算法課程 (陳士杰)

補充

國立聯合大學資訊管理學系演算法課程 (陳士杰)

▓各類問題的說明

 SAT Problem (The Satisfiability Problem; 滿足問題):

 給一個具CNF型式的布林函數E，判斷是否存在一組解，使得此函

數為True。若存在則稱此函數為Satisfiable。

{ CNF (Conjunction Normal Form)型式：括號內的變數皆以or運算 (∨)

相連，而括號間則以and運算(∧)相連的函數型式稱之。

 Ex:

{ Let E = (-x

∨ x

∨-x

)∧(x

∨ -x

) ∧(x

∨ x

). Then the following

assignment will make E true, and the answer will be “

yes

yes”.

←F, x

←T

{ If E = (-x

∧ x

) , there will be no assignment which can make E true,

and the answer will be “

no”.

 此問題為第一個被証明是屬於

Complete

Complete的問題 (by S. A. Cook,

1971).

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 3-SAT Problem (Three Variables SAT Problem):

 給予一個具CNF型式的布林函數，且其中每組Clause(和項)都只包

含三個變數，判斷是否存在一組解，使得此函數為True

。若存在

則稱此函數為Satisfiable。

{ E = (-x

∨ x

∨-x

)∧(x

∨ -x

) 為3-SAT

{ E = (-x

∨ x

∨-x

)∧(x

∨ -x

) 不為3-SAT

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Clique (結黨; 派系)

 一個無向圖 (Undirected Graph) G = (V, E)中，存在一個子圖

(Sub-graph) G’，且此子圖G’為一個完整圖 (Complete Graph)，則

G’的頂點集合即為G的Clique。

{ Complete Graph:

 一個 “任兩個頂點間皆有一個邊相連” 之圖形稱之。

 即：當一個Complete Graph有n個頂點時，該圖形的邊之個數共

有 n(n-1)/2條。

 Clique Problem:

 給予一個Undirected Graph G及一個整數 k (其中k>0)，判斷在G

中是否可找到一個頂點個數≥k的Clique。

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Ex:有一圖形G如下：

請問在G中是否可找到一個頂點個數≥3的Clique?

Ans: 可以

Clique

Not Clique

國立聯合大學資訊管理學系演算法課程 (陳士杰)

 Vertex-Cover (頂點覆蓋)

 一個圖形G的Vertex Cover為一組頂點集合C.

 圖形G中每個邊所相連的兩個頂點(u, v)，至少會有一個位於此頂

點集合C當中。表示這個頂點集合C可以Cover圖形G中所有的邊。

 Ex:

{a, d, e}為此圖的Vertex Cover

 Vertex Cover Problem:

 給予一個無向圖G與一個整數k，判斷在圖形G中是否可找到一個

頂點個數≤k的頂點集合C，使得G中所有的邊皆至少有一個相連頂

點位於此集合C中。